#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;

//121.买卖股票的最佳时机
//7 1 5 3 6 4
int maxProfit(vector<int>& prices){
    //minnum表示最低的买价，ret表示最高的利润
    int minnum = INT_MAX, ret = INT_MIN;

    for(auto x : prices){
        ret = max(ret, x - minnum);
        minnum = min(minnum, x);
    }
    if(ret<0){
        return 0;
    }

    return ret;
}

//122.买卖股票的最佳时机2
//方法一：
int maxProfit(vector<int>& prices){
    //使用双指针找到上升趋势的最低点和最高点进行买卖
    int ret = 0;

    for (int buy = 0; buy < prices.size(); buy++){
        //卖指针从买指针位置开始找
        int sell = buy;

        //找到上身趋势的最高点
        while(sell+1<prices.size()&&prices[sell]<prices[sell+1]){
            sell++;
        }

        //在当前位置买卖
        ret += prices[sell] - prices[buy];
        //更新买指针指向当前位置
        buy = sell;
    }

    return ret;
}
//方法二：
int maxProfit(vector<int>& prices){
    //在上升趋势段，一天一天地买卖获取利润
    int ret = 0;

    for (int i = 0; i < prices.size(); i++){
        //如果下一个值大于当前值，就直接买卖
        if(i+1<prices.size()&&prices[i+1]>prices[i]){
            ret += prices[i + 1] - prices[i];
        }
    }

    return ret;
}

//3 -1 0 2   3
//1005.k次取反后最大化的数组和
struct Greater{
    bool operator()(const int p1,const int p2){
        return p1 > p2;
    }
};
int largestSumAfterKNegations(vector<int>& nums, int k){
    //建立一个小根堆
    priority_queue<int, vector<int>, Greater> heap(nums.begin(), nums.end());

    while(k>0){
        //获取堆顶元素
        int t = heap.top();
        heap.pop();
        //如果堆顶元素是负数，修改为正数
        if(t<0){
            heap.push(-t);
            k--;
        }
        //如果堆顶元素是正数，先判断当前剩余次数
        else{
            //如果次数为奇数，修改最小的正数为负数，次数减一，剩余次数就是偶数
            //下一个正数进行偶数次的变换,相当于不变，直接结束
            if(k%2==1){
                heap.push(-t);
                k = 0;
            }
            //如果剩余偶数次，当前正数变化完所有次数，相当于不变，直接结束
            else{
                k = 0;
            }

        }
    }

    int ret = 0;
    while(!heap.empty()){
        ret+=heap.top();
        heap.pop();
    }
    return ret;
}

//2418.按身高排序
vector<string> sortPeople(vector<string>& names, vector<int>& heights){
    //建立一个下标数组
    int n = names.size();
    vector<int> index(n);
    for (int i = 0; i < n; i++){
        index[i] = i;
    }

    //对下标数组进行排序
    sort(index.begin(), index.end(), [&](const int i, const int j){
        return heights[i] > heights[j]; 
    });

    //提取结果
    vector<string> ret;
    for(auto i : index){
        ret.push_back(names[i]);
    }

    return ret;
}

//优势洗牌
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2){
    int n = nums1.size(), m = nums2.size();
    //给数组2创建一个下标数组
    vector<int> index(m);
    for (int i = 0; i < m; i++){
        index[i] = i;
    }

    // 数组1直接排序，数组2通过下标数组排序,排升序
    sort(nums1.begin(), nums1.end());
    sort(index.begin(), index.end(), [&](const int i, const int j) {
        return nums2[i] < nums2[j]; 
    });

    //创建一个结果数组用来存放数组1按题意要求的排序
    vector<int> ret(n);

    //两个指针用来指向下标数组的前后位置
    int left = 0, right = m - 1;
    for (int i = 0; i < ; i++){
        //如果第一个数组的值大于第二个数组的当前值，左指针指向下标数组中的位置就是结果数组中存放的下标
        if(nums1[i]>nums2[index[left]]){
            ret[index[left++]] = nums1[i];
        }
        //如果小于等于，存放到右指针指向的下标位置
        else{
            ret[index[right--]] = nums1[i];
        }
    }

    return ret;
}

int main(){

    return 0;
}